import heapq
import random
import time
from itertools import combinations


def greedy_min_max_subsequence_sum(nums, k):
    """贪心算法：使用最小堆分配元素"""
    n = len(nums)
    if k > n: return -1
    if k <= 0: return -1
    if k == 1: return sum(nums)

    nums.sort(reverse=True)  # 从大到小排序

    heap = [0] * k  # 初始化k个空子序列
    heapq.heapify(heap)
    max_sum = 0

    for num in nums:
        current_min = heapq.heappop(heap)
        new_sum = current_min + num
        heapq.heappush(heap, new_sum)
        if new_sum > max_sum:
            max_sum = new_sum

    return max_sum


def brute_force_min_max_subsequence_sum(nums, k):
    """暴力搜索：尝试所有划分方式（仅适用于小规模数据）"""
    n = len(nums)
    if k > n: return -1
    if k <= 0: return -1
    if k == 1: return sum(nums)

    total = sum(nums)
    best = float('inf')

    # 生成所有可能的分割点组合
    for splits in combinations(range(1, n), k - 1):
        splits = sorted(splits)
        partitions = []
        start = 0
        max_sum = 0

        # 根据分割点创建子序列
        for end in splits:
            partition = nums[start:end]
            s = sum(partition)
            if s > max_sum: max_sum = s
            start = end
        partition = nums[start:]
        s = sum(partition)
        if s > max_sum: max_sum = s

        if max_sum < best:
            best = max_sum

    return best


def generate_test_case(max_len=10, max_val=100):
    """生成随机测试用例"""
    n = random.randint(1, max_len)
    k = random.randint(1, n)
    nums = [random.randint(1, max_val) for _ in range(n)]
    return nums, k


def run_test(num_tests=1000):
    """运行对拍测试"""
    passed = 0
    failed = 0
    longest_time_bf = 0
    longest_time_greedy = 0

    for i in range(num_tests):
        nums, k = generate_test_case(max_len=40, max_val=1000)

        # 运行贪心算法
        start = time.time()
        greedy_result = greedy_min_max_subsequence_sum(nums[:], k)
        greedy_time = time.time() - start
        longest_time_greedy = max(longest_time_greedy, greedy_time)

        # 运行暴力搜索（仅当n<10时）
        brute_result = None
        if len(nums) <= 1000:
            start = time.time()
            brute_result = brute_force_min_max_subsequence_sum(nums[:], k)
            bf_time = time.time() - start
            longest_time_bf = max(longest_time_bf, bf_time)

            # 比较结果
            if greedy_result != brute_result:
                # print(f"\n❌ 测试失败 #{i + 1}")
                # print(f"输入: nums={nums}, k={k}")
                # print(f"贪心结果: {greedy_result}")
                # print(f"暴力结果: {brute_result}")
                failed += 1
                continue

        passed += 1
        if (i + 1) % 100 == 0:
            print(f"✓ 已通过 {i + 1} 个测试", end='\r')

    print("\n\n对拍器测试结果:")
    print(f"总测试数: {num_tests}")
    print(f"通过: {passed} ({passed / num_tests * 100:.1f}%)")
    print(f"失败: {failed}")
    print(f"最长贪心时间: {longest_time_greedy * 1000:.3f}ms")
    if longest_time_bf > 0:
        print(f"最长暴力时间: {longest_time_bf * 1000:.3f}ms")


# 运行对拍测试
if __name__ == "__main__":
    print("开始对拍测试...")
    run_test(num_tests=100)

    # 额外测试一些已知用例
    test_cases = [
        ([7, 2, 5, 10, 8], 2, 17),
        ([1, 2, 3, 4, 5, 6], 3, 7),
        ([1, 1, 1, 1, 1, 1], 3, 2),
        ([10, 20, 30], 2, 30),
        ([100, 200, 300, 400, 500, 600, 700, 800, 900], 3, 1700),
        ([1, 2, 3, 4, 5], 5, 5),
        ([10, 10, 10, 10], 4, 10),
        ([5, 4, 3, 2, 1], 2, 8)
    ]

    print("\n已知用例测试:")
    for i, (nums, k, expected) in enumerate(test_cases):
        result = greedy_min_max_subsequence_sum(nums, k)
        status = "✓" if result == expected else "❌"
        print(f"测试 {i + 1}: {status} 输入={nums}, k={k}, 期望={expected}, 得到={result}")
